class Solution {
    int n,m;

public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    void dfs(int x,int y,vector<vector<char>>& grid)
    {
        grid[x][y]='0';
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m || grid[nx][ny]=='0')
            {
                continue;
            }
            dfs(nx,ny,grid);
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int ret=0;
        n=grid.size();
        m=grid[0].size();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]=='1')
                {
                    ret++;
                    dfs(i,j,grid);
                }
            }
        }  
        return ret; 
    }
};
